Computer-generated imagery typically involves using software and/or hardware to generate one or more images from a geometric model. A geometric model defines objects, light sources, and other elements of a virtual scene and a rendering system or other computer/software/hardware system will read in the geometric model and determine what colors are needed in what portions of the image. A renderer will generate a two-dimensional (“2D”) array of pixel color values that collectively result in the desired image or images.
For a simple geometric model, such as a cube in a vacuum with a single light source, a simple computer program running on most computer hardware could render the corresponding image in a reasonable amount of time without much optimization effort. However, there are many needs—in the entertainment industry and beyond—for methods and apparatus that can efficiently process complex interactions of virtual objects to generate imagery in constrained timeframes where the images might need to convey realistic light interactions, such as light interacting with a participating medium. In some cases, the rendering is needed in real-time, i.e., situations where the geometric model is not available well in advance (such as when the geometric model depends on unpredictable actions taken by a user) and yet the image needs to be generated right then. This places severe strains on computer processing hardware and software.
In real world scenes, moisture or dust in the air often results in visible volumetric shadows and beams of light known as “god rays” or “crepuscular rays.” Rendering these light scattering effects in an image of a virtual space is often essential for producing compelling virtual scenes. Simulating all scattering events is prohibitively expensive, especially for real-time applications, and approximations are used instead.
The “single-scattering” model [Blinn1982] greatly simplifies rendering, while still producing realistic effects. In this model, a light ray is modeled as travelling from a source, and may get scattered into the eye at any point in the participating medium, while attenuating along the path. This simplification has allowed participating media with shadows to make its way into modern computer games. Typically, the scattering medium is assumed to be homogeneously distributed through the scene.
The simplest method for rendering single scattering is ray marching. In ray marching, the rendering system calculates pixel values by considering a ray cast from the camera eye through each pixel and approximating a scattering integral by “marching” along that ray and checking if each sample is lit or shadowed using a shadow map. To generate high-quality images, however, many samples are needed. Several methods for accelerating this process have been published in the last couple of years. [Baran2010] shows some examples.
There have been several papers written on solving the single-scattering integral (semi)-analytically [Sun2005; Pegoraro2009; Pegoraro2010], but they necessarily ignore shadowing, which is often required for realism. Other methods, such as volumetric photon mapping [Jensen1998; Jarosz2008] and line space gathering [Sun2010] compute solutions to more difficult scattering problems, such as volumetric caustics or multiple scattering, but even with graphical processing unit (“GPU”) acceleration they are far from real-time on complex scenes.
Max [Max1986] described how to compute the single-scattering integral by finding the lit segments on each ray using shadow volumes intersected with epipolar slices. The integral on each lit segment is computed analytically. Epipolar sampling [Engelhardt2010] speeds up ray marching by computing it only at depth discontinuities along image-space epipolar lines. The scattered radiance at all other points is interpolated along these lines, but this can cause temporally-varying artifacts, as discussed in prior work [Baran2010]. Wyman and Ramsey [Wyman2008] use shadow volumes to cull ray marching in unlit areas. Hu et al. [Hu2010] recently presented an algorithm for interactive volumetric caustics, using Wyman and Ramsey's [Wyman2008] method for single scattering. Though this method works well for simple occluders, it becomes slow in the presence of complex visibility boundaries. Several methods [Dobashi2000; Dobashi2002] compute the scattering integral by constructing slices at different depths, rendering the scattering at these slices, and using alpha-blending to combine them. Imagire and colleagues [Imagire2007] use a hybrid approach that incorporates both slices and ray marching.
The algorithm of Billeter et al. [Billiter2010] is similar to that of Max [Max1986], but generates the shadow volume from the shadow map and uses the GPU rasterizer to compute the lit segments. This latter method is exact up to the shadow map resolution. It is very fast for low-resolution shadow maps, but slows down significantly for higher resolution shadow maps (such as 40962 resolution) and the number of vertices in the shadow volume overwhelms the pipeline. Unfortunately, large and complex scenes of interest require such high-resolution shadow maps to avoid aliasing.
For high-resolution shadow maps, Billeter et al. perform online decimation of the shadow volume, but this is expensive and has their outer loop over the shadow volume elements, which can require sending a large number of vertices to a GPU. The algorithm of Baran et al. [Baran2010] (referred to herein as “incremental integration”) uses epipolar rectification to reduce scattering integration to partial sums on a rectilinear grid and uses a partial sum tree to accelerate this computation. While this method has good worst-case upper bounds and is very fast on a CPU, it requires an incremental traversal of multiple camera rays in a particular order, making it difficult to utilize the full parallelism provided by a GPU. Implementing their method on a GPU also requires using a GPGPU API, such as CUDA or OpenCL, but that constrains the hardware that can be used for rendering
Min-max mipmaps have been used for accelerating soft shadows [Guennebaud2006], global illumination [Nichols2009], as well as ray tracing geometry images [Carr2006] and height fields [Mastin1987; Musgrave1989; Tevs2008], but these are two-dimensional (“2D”) mipmaps and are not all that simple and efficient.
Thus, even with those techniques, there was room for improvement.